0% completed
Problem Statement
Given a string s, representing the mathematical expression, evaluate the expression and return the integer value.
The integer division should truncate toward zero.
*Note: You are not allowed to use the built-in functions like eval().
Examples
Example 1:
- Input:
"8*5/4+3-2" - Expected Output:
11 - Justification: The calculation proceeds as follows:
8*5 = 40,40/4 = 10,10+3 = 13,13-2 = 11.
Example 2:
- Input:
"10+20/5*3" - Expected Output:
22 - Justification: The order of operations gives
20/5 = 4,4*3 = 12, and10+12 = 22.
Example 3:
- Input:
"50-25+5*3/2*2-10/2" - Expected Output:
34 - Justification: Following the order of operations:
50 - 25 = 25,(15/2) = 7(rounded down),7*2 = 14,25+14 = 39,10/2 = 5, and39 - 5 = 34.
Solution
To solve this problem, our approach blends linear parsing with immediate evaluation of arithmetic operations. This methodology effectively addresses the challenge of respecting the standard order of operations (multiplication and division prior to addition and subtraction) within a single pass through the expression. The logic behind this approach is to evaluate and accumulate partial results as soon as possible, especially when dealing with multiplication and division, which have higher precedence.
The efficiency of this method lies in its ability to process the expression in a single sweep, thereby minimizing the need for backtracking or re-evaluating portions of the expression. By updating the cumulative result and the last evaluated number at each step, based on the current operation, the algorithm ensures that the most recent operation is always applied correctly. This real-time processing approach not only maintains the correct order of operations but also streamlines the computational process, leading to a solution that is both time and space-efficient.
Step-by-Step Algorithm
- Initialize
currentNumber,lastNumber, andresultto 0, and setoperationto '+'. - Iterate over each character in the input string:
- If the character is a digit, update
currentNumberaccordingly. - If the character is a non-digit, non-space, or it's the end of the string:
- If
operationis '+' or '-', addlastNumbertoresult. UpdatelastNumbertocurrentNumberor-currentNumberbased onoperation. - If
operationis '*', multiplylastNumberwithcurrentNumber. - If
operationis '/', dividelastNumberbycurrentNumber. - Update
operationto the current character. - Reset
currentNumberto 0.
- If
- If the character is a digit, update
- After the loop, add
lastNumbertoresultfor the final total.
Algorithm Walkthrough
let's consider input: "50-25+5*3/2*2-10/2"
Certainly, let's correct the walkthrough of the code with the input "50-25+5*3/2*2-10/2". We'll carefully trace through the arithmetic and ensure accurate computation at each step.
-
Initialization:
currentNumber = 0,lastNumber = 0,result = 0,operation = '+'.
-
Processing each character:
- Iterate through each character of the string.
-
First Character '5':
currentNumberbecomes 5.
-
Second Character '0':
currentNumberbecomes 50.
-
Third Character '-':
- Operation is
+, solastNumber = 50(ascurrentNumberis 50). resultbecomes 0 (0 + 0).operationupdated to '-'.currentNumberreset to 0.
- Operation is
-
Next Characters '25':
currentNumberbecomes 25.
-
Character '+':
- Operation is '-', so
lastNumber = -25. resultbecomes 50 (0 + 50).operationupdated to '+'.currentNumberreset to 0.
- Operation is '-', so
-
Next Characters '5':
currentNumberbecomes 5.
-
Character '*':
- Operation is '+',
resultbecomes 25 (50 - 25). - Update `lastNumber = 5
operationupdated to '*'.currentNumberreset to 0.
- Operation is '+',
-
Next Characters '3':
currentNumberbecomes 3.
-
Character '/':
- Operation is '*', so
lastNumberbecomes 15 (5 * 3). operationupdated to '/'.currentNumberreset to 0.
- Operation is '*', so
-
Next Characters '2':
currentNumberbecomes 2.
-
Character '*':
- Operation is '/', so
lastNumberbecomes 7 (15 / 2, rounded down for integer division). operationupdated to '*'.currentNumberreset to 0.
- Operation is '/', so
-
Next Characters '2':
currentNumberbecomes 2.
-
Character '-':
- Operation is '*', so
lastNumberbecomes 14 (7 * 2). resultbecomes 39 (25 + 14).operationupdated to '-'.currentNumberreset to 0.
- Operation is '*', so
-
Next Characters '10':
currentNumberbecomes 10.
-
Character '/':
- Operation is '-', so
lastNumberbecomes -10. resultremains 39.operationupdated to '/'.currentNumberreset to 0.
- Operation is '-', so
-
Next Characters '2':
currentNumberbecomes 2.
-
End of String:
- Operation is '/', so
lastNumberbecomes -5 (10 / 2, integer division). resultbecomes 34 (39 - 5).
- Operation is '/', so
-
Final Calculation:
resultis 34.
Code
Complexity Analysis
-
Time Complexity: The algorithm has a linear time complexity of
O(N), where N represents the length of the input string. This is because the algorithm processes each character in the string exactly once. -
Space Complexity: The space complexity of the algorithm is
O(1), or constant space complexity. This is due to the use of a fixed number of variables regardless of the size of the input string.
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis